【题解】 [ICPC-Beijing 2006]狼抓兔子 网络流 bzoj1001/洛谷P4001 | Qiuly's blog!

【题解】 [ICPC-Beijing 2006]狼抓兔子 网络流 bzoj1001/洛谷P4001

Posted on | Edited on | In | Comments:

网络流水题。

既然要抓到所有的兔子，又要用最少的狼，很容易想到，这是在让我们求最小割。

那么如何求最小割呢？

有一条定理是这样的：最大流=最小割

所以我们只要用 $Dinic$ 跑出最大流，然后直接输出就行了。

不过，为什么最大流=最小割呢？

网上的一名 $Dalao$ 给出了答案：

$Q:$ 如何凭直觉解释最大流等于最小割?

$A:$ $1.$ 最大流不可能大于最小割, 因为最大流所有的水流都一定经过最小割那些割边, 流过的水流怎么可能比水管容量还大呢? $2.$ 最大流不可能小于最小割, 如果小, 那么说明水管容量没有物尽其用, 可以继续加大水流.

$Q:$ 如何严谨证明最大流等于最小割?

$A:$ $1.$ 证明任意的 $s-t$ 流量小于 $s-t$ 割容量, 证明方法: 根据定义即可; $2.$ 根据 $Ford-Fulkerson$ 算法求出的流来选出一个 $s-t$ 割, $S$ 为残余网络中 $s$ 可达的顶点集合, 这样就可以证出算法求出的流$=$这个割的容量, 再根据已经证明的 $1$ 来得出算法求出的流是最大流, 对应的割是最小割.

$Dalao——Jecvay Notes$

现在要注意的一点就是，直接跑朴素的 $Dinic$ 是会 T 的，这个时候或许会要一些优化，比如说用当前弧优化，或者可以跑$ISAP$，如果还过不了，吸氧算了[滑稽]。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<bits/stdc++.h>
#define RI register int
#define ll long long
const int N=1e6+2;
const int inf=1e9+9;

struct Edge{
    int nxt,to,val;
}G[N*6];
int n,m,s,t,cnt=1,dep[N],head[N];

#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y)) 
template <typename _Tp> inline void IN(_Tp&x){
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch))if(ch=='-')flag=1;
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    if(flag)x=-x;
}

inline int id(int x,int y){return (x-1)*m+y;}
inline void add(int x,int y,int v){
    G[++cnt].nxt=head[x],G[cnt].to=y,G[cnt].val=v,head[x]=cnt;
    G[++cnt].nxt=head[y],G[cnt].to=x,G[cnt].val=v,head[y]=cnt;
}

inline bool bfs(){
    std::memset(dep,0,sizeof(dep));
    std::queue<int>q;q.push(s),dep[s]=1;
    while(!q.empty()){
        int x=q.front();q.pop();
        for(int i=head[x];i;i=G[i].nxt){
            int y=G[i].to;
            if(dep[y]||!G[i].val)continue;
            dep[y]=dep[x]+1;q.push(y);
            if(y==t)return true; 
        }
    }return false;
}
inline int dfs(int x,int flow){
    if(x==t)return flow;
    int used=0;
    for(int i=head[x];i&&used<flow;i=G[i].nxt){
        int y=G[i].to;
        if(dep[y]!=dep[x]+1||!G[i].val)continue; 
        else{
            int rlow=dfs(y,min(G[i].val,flow-used));
            if(!rlow){dep[y]=-1;continue;}
            G[i].val-=rlow,G[i^1].val+=rlow,used+=rlow;
        }
    }return used;
}
inline int Dinic(){
    int ans=0;
    while(bfs())ans+=dfs(s,inf);
    return ans;
}

int main(){
    int v;
    IN(n),IN(m);s=1,t=n*m;
    for(int i=1;i<=n;++i)
       for(int j=2;j<=m;++j)
          IN(v),add(id(i,j-1),id(i,j),v);
    for(int i=2;i<=n;++i)
       for(int j=1;j<=m;++j)
          IN(v),add(id(i-1,j),id(i,j),v);
    for(int i=2;i<=n;++i)
       for(int j=2;j<=m;++j)
          IN(v),add(id(i-1,j-1),id(i,j),v);
    printf("%d\n",Dinic());
    return 0;
}

本文标题:【题解】 [ICPC-Beijing 2006]狼抓兔子 网络流 bzoj1001/洛谷P4001

文章作者:Qiuly

发布时间:2019年02月14日 - 00:00

最后更新:2019年03月29日 - 13:54

原始链接:http://qiulyblog.github.io/2019/02/14/[题解]luoguP4001/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。